package code;

import java.util.ArrayList;

public class Test{
	
    public int trap(int A[]) {

        int ans=0;
        ArrayList<Integer> peekIndex=new ArrayList<>();
        int n=A.length;
        int[] sum=new int[n];
        int i,j,k;
        //�ҷ�ֵ��
        if(n<3)	return ans;
        
        for(i=0;i<n;i++){
        	if(i==0 && A[i]>A[i+1])	peekIndex.add(i);
        	if(i==n-1 && A[i]>A[i-1])	peekIndex.add(i);
        	if(i>0 && i<n-1){
        		if(A[i]>A[i-1] && A[i]>A[i+1] 
        				|| A[i]>A[i-1] && A[i]==A[i+1] 
        				||	A[i]==A[i-1] && A[i]>A[i+1]
        				)
        			peekIndex.add(i);
        	}
        	sum[i]=A[i];
        	if(i>0)	sum[i]+=sum[i-1];
        }
        
        for(i=0;i<peekIndex.size();){
        	/*
        	 * �ҵ�һ�����Լ������
        	 * ���û�ҵ��ұߵ�һ����A[i]����������ұ�������
        	 */
        	int max=0;
        	for(j=i+1;j<peekIndex.size();j++){
        		//��¼�ұ�����һ��ֵ
        		if(max<A[peekIndex.get(j)])	
        			max=peekIndex.get(j);
        		
        		if(A[peekIndex.get(i)]<=A[peekIndex.get(j)]){
        			break;
        		}
        	}
        	//x<=y
        	if(j<peekIndex.size()){
        		ans+=A[peekIndex.get(i)]*(peekIndex.get(j)-peekIndex.get(i)-1);
        		int t1=sum[peekIndex.get(j)-1];
        		int t2=sum[peekIndex.get(i)];
        		ans-=(sum[peekIndex.get(j)-1]-sum[peekIndex.get(i)]);
        		i=j;
        	}
        	//x>y
        	else{
        		if(max==0)	break;
        		ans+=A[max]*(max-peekIndex.get(i)-1);
        		ans-=(sum[max-1]-sum[peekIndex.get(i)]);
        		i=max;
        	}
        }
        
    	return ans;
    }
    public int compareVersion(String version1, String version2) {
        String[] v1=version1.split("\\.");
        String[] v2=version2.split("\\.");
        for(int i=0;i<v1.length && i<v2.length;i++){
        	int x=Integer.valueOf(v1[i]);
        	int y=Integer.valueOf(v2[i]);
        	if(x>y)	return 1;
        	if(x<y)	return -1;
        }
        if(v1.length>v2.length){
        	int x=Integer.valueOf(v1[v2.length]);
        	if(x>0)	return 1;
        }
        if(v1.length<v2.length){
        	int x=Integer.valueOf(v2[v1.length]);
        	if(x>0)	return -1;
        }
        return 0;
    } 
    public static void main(String[] args){
    	String s="10.6.5";
    	String t="10.6";
    	Test ts=new Test();
    	System.out.println(ts.compareVersion(s, t));
//    	int n=2;
//    	int bitCount=0;
//    	int y=(2&2);
//    	System.out.println(y);
//    	for(int i=0;i<32;i++){
//    		if(((1<<i)&n)!=0)	bitCount++;
//    		int x=(1<<i);
//    		System.out.println(i+" "+x+"  "+bitCount);
//    	}
//    	Test test=new Test();
//    	int[] A={0,1,0,2,1,0,1,3,2,1,2,1};
//    	int[] a={5,4,1,2};
//    	
//    	int ans=test.trap(a);
//    	System.out.println(ans);
    }
}
